{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Distance in a Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到二叉树中的距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉树的根节点 <code>root</code> 以及两个整数 <code>p</code> 和 <code>q</code> ，返回该二叉树中值为 <code>p</code> 的结点与值为 <code>q</code> 的结点间的 <strong>距离 </strong>。</p>\n",
    "\n",
    "<p>两个结点间的<strong> 距离 </strong>就是从一个结点到另一个结点的路径上边的数目。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2018/12/14/binarytree.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 0\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>在 5 和 0 之间有 3 条边：5-3-1-0</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2018/12/14/binarytree.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 7\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>在 5 和 7 之间有 2 条边：5-2-7</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2018/12/14/binarytree.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 5\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>一个结点与它本身之间的距离为 0</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中结点个数的范围在 <code>[1, 10<sup>4</sup>]</code>.</li>\n",
    "\t<li><code>0 <= Node.val <= 10<sup>9</sup></code></li>\n",
    "\t<li>树中所有结点的值都是唯一的.</li>\n",
    "\t<li><code>p</code> 和<code>q</code> 是树中结点的值.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-distance-in-a-binary-tree](https://leetcode.cn/problems/find-distance-in-a-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-distance-in-a-binary-tree](https://leetcode.cn/problems/find-distance-in-a-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5,1,6,2,0,8,null,null,7,4]\\n5\\n0', '[3,5,1,6,2,0,8,null,null,7,4]\\n5\\n7', '[3,5,1,6,2,0,8,null,null,7,4]\\n5\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "\n",
    "        def find_root(val):\n",
    "            res = [root]\n",
    "            vals = [[root.val]]\n",
    "            if root.val==val:\n",
    "                return [val]\n",
    "            while res:\n",
    "                new_vals = []\n",
    "                new_res = []\n",
    "                for i,x in enumerate(res):\n",
    "                    if x.left:\n",
    "                        if x.left.val == val:\n",
    "                            return vals[i]+[val]\n",
    "                        else:\n",
    "                            new_vals.append(vals[i]+[x.left.val])\n",
    "                            new_res.append(x.left)\n",
    "                    \n",
    "                    if x.right:\n",
    "                        if x.right.val == val:\n",
    "                            return vals[i]+[val]\n",
    "                        else:\n",
    "                            new_vals.append(vals[i]+[x.right.val])\n",
    "                            new_res.append(x.right)\n",
    "                res = new_res\n",
    "                vals = new_vals\n",
    "            return -1\n",
    "        \n",
    "        root_p = find_root(p)\n",
    "        root_q = find_root(q)\n",
    "        common = [x for x in root_p if x in root_q][-1]\n",
    "        dist1 = len(root_p)-root_p.index(common)-1\n",
    "        dist2 = len(root_q)-root_q.index(common)-1\n",
    "\n",
    "        res = dist1+dist2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        LCA = self.find_LCA(root, p, q)\n",
    "\n",
    "        p_deep = self.dfs(LCA, p)\n",
    "        q_deep = self.dfs(LCA, q)\n",
    "        return p_deep+q_deep\n",
    "    \n",
    "    def dfs(self, root, target):\n",
    "        if root == None:\n",
    "            return -1\n",
    "        if root.val == target:\n",
    "            return 0\n",
    "        L = self.dfs(root.left, target)\n",
    "        R = self.dfs(root.right, target)\n",
    "        \n",
    "        if L == -1 and R == -1:\n",
    "            return -1\n",
    "        return max(L , R) + 1\n",
    "    \n",
    "    def find_LCA(self, root, p, q):\n",
    "        if not root or root.val == p or root.val == q:\n",
    "            return root\n",
    "        L = self.find_LCA(root.left, p, q)\n",
    "        R = self.find_LCA(root.right, p, q)\n",
    "        if L and R:\n",
    "            return root\n",
    "        elif L and R==None:\n",
    "            return L\n",
    "        elif L == None and R:\n",
    "            return R\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        # time complexity: o(n) + 2*o(n) = o(n)\n",
    "        # space complexity: o(n)\n",
    "\n",
    "        # 先寻找lca，再计算各点到lca的距离\n",
    "        if p == q:\n",
    "            return 0\n",
    "\n",
    "        def lca(node, p, q):\n",
    "            if not node:\n",
    "                return None\n",
    "            \n",
    "            if node.val == p or node.val == q:\n",
    "                return node\n",
    "\n",
    "            left = lca(node.left, p, q)\n",
    "            right = lca(node.right, p, q)\n",
    "\n",
    "            if left and right:\n",
    "                return node\n",
    "            \n",
    "            return left if left else right\n",
    "        \n",
    "        def get_depth(node, p):\n",
    "            if not node:\n",
    "                return -1\n",
    "            \n",
    "            if node.val == p:\n",
    "                return 0\n",
    "            \n",
    "            left = get_depth(node.left, p)\n",
    "            right = get_depth(node.right, p)\n",
    "\n",
    "            result = max(left, right)\n",
    "            return result + 1 if result >= 0 else -1\n",
    "\n",
    "        parent = lca(root, p, q)\n",
    "        distance = get_depth(parent, p) + get_depth(parent, q)\n",
    "\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        def dfs(node, target):\n",
    "            if node is None:\n",
    "                return inf\n",
    "            if node.val == target:\n",
    "                return 0\n",
    "            l = dfs(node.left, target)\n",
    "            r = dfs(node.right, target)\n",
    "            return min(l, r) + 1\n",
    "        def find(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.val == p or node.val == q:\n",
    "                return node\n",
    "            l = find(node.left)\n",
    "            r = find(node.right)\n",
    "            if l and r:\n",
    "                return node\n",
    "            if l:\n",
    "                return l\n",
    "            if r:\n",
    "                return r\n",
    "        parent = find(root)\n",
    "        return dfs(parent, p) + dfs(parent, q)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def findDistance(self, root: TreeNode, p: int, q: int) -> int:\r\n",
    "        LCA = self.find_LCA(root, p, q)     #Least Common Ancestor\r\n",
    "        \r\n",
    "        p_dep = self.dfs(LCA, p)\r\n",
    "        q_dep = self.dfs(LCA, q)\r\n",
    "        return p_dep + q_dep\r\n",
    "\r\n",
    "    def dfs(self, root: TreeNode, target: int) -> int:\r\n",
    "        if root == None:\r\n",
    "            return -1\r\n",
    "        if root.val == target:\r\n",
    "            return 0\r\n",
    "        L = self.dfs(root.left, target)\r\n",
    "        R = self.dfs(root.right, target)\r\n",
    "        \r\n",
    "        if L == -1 and R == -1:\r\n",
    "            return -1\r\n",
    "        return max(L , R) + 1\r\n",
    "\r\n",
    "    def find_LCA(self, root: TreeNode, p: int, q: int) -> TreeNode:\r\n",
    "        if root==None or root.val==p or root.val==q:\r\n",
    "            return root\r\n",
    "        L = self.find_LCA(root.left, p, q)\r\n",
    "        R = self.find_LCA(root.right, p, q)\r\n",
    "        if L and R:\r\n",
    "            return root\r\n",
    "        elif L and R==None:\r\n",
    "            return L\r\n",
    "        elif L == None and R:\r\n",
    "            return R\r\n",
    "        else:\r\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        def lca(root):\n",
    "            if not root or root.val in [p,q]:\n",
    "                return root\n",
    "            left,right = lca(root.left),lca(root.right)\n",
    "            if left and right:\n",
    "                return root\n",
    "            return left if left else right\n",
    "\n",
    "        def dfs(root,val):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if root.val == val:\n",
    "                return 1\n",
    "            left = dfs(root.left,val)\n",
    "            right = dfs(root.right,val)\n",
    "            return 1+max(left,right) if left or right else 0\n",
    "\n",
    "        root = lca(root)\n",
    "        return dfs(root,p)+dfs(root,q)-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: TreeNode, p: int, q: int) -> int:\n",
    "        LCA = self.find_LCA(root, p, q)     #Least Common Ancestor\n",
    "        p_dep = self.dfs(LCA, p)\n",
    "        q_dep = self.dfs(LCA, q)\n",
    "        return p_dep + q_dep\n",
    "\n",
    "    def dfs(self, root: TreeNode, target: int) -> int:\n",
    "        if root == None:\n",
    "            return -1\n",
    "        if root.val == target:\n",
    "            return 0\n",
    "        L = self.dfs(root.left, target)\n",
    "        R = self.dfs(root.right, target)\n",
    "        if L == -1 and R == -1:\n",
    "            return -1\n",
    "        return max(L , R) + 1\n",
    "\n",
    "    def find_LCA(self, root: TreeNode, p: int, q: int) -> TreeNode:\n",
    "        if root==None or root.val==p or root.val==q:\n",
    "            return root\n",
    "        L = self.find_LCA(root.left, p, q)\n",
    "        R = self.find_LCA(root.right, p, q)\n",
    "        if L and R:\n",
    "            return root\n",
    "        else:\n",
    "            return L or R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def find_LCA(self, root: TreeNode, p: int, q: int) -> TreeNode:\n",
    "        if root==None or root.val==p or root.val==q:\n",
    "            return root\n",
    "        L = self.find_LCA(root.left, p, q)\n",
    "        R = self.find_LCA(root.right, p, q)\n",
    "        if L and R:\n",
    "            return root\n",
    "        elif L and R==None:\n",
    "            return L\n",
    "        elif L == None and R:\n",
    "            return R\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    \n",
    "    def depth2tar(self, root, target):\n",
    "        if not root:\n",
    "            return -1\n",
    "        if root.val == target:\n",
    "            return 0\n",
    "        L = self.depth2tar(root.left, target)\n",
    "        R = self.depth2tar(root.right, target)\n",
    "\n",
    "        if L == -1 and R == -1:\n",
    "            return -1\n",
    "        \n",
    "        return max(L, R) + 1\n",
    "\n",
    "\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "\n",
    "        lca_node = self.find_LCA(root, p, q)\n",
    "        dep_p = self.depth2tar(lca_node, p)\n",
    "        dep_q = self.depth2tar(lca_node, q)\n",
    "        return dep_p + dep_q\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: TreeNode, p: int, q: int) -> int:\n",
    "        LCA = self.find_LCA(root, p, q)     #Least Common Ancestor\n",
    "        \n",
    "        p_dep = self.dfs(LCA, p)\n",
    "        q_dep = self.dfs(LCA, q)\n",
    "        return p_dep + q_dep\n",
    "\n",
    "    def dfs(self, root: TreeNode, target: int) -> int:\n",
    "        if root == None:\n",
    "            return -1\n",
    "        if root.val == target:\n",
    "            return 0\n",
    "        L = self.dfs(root.left, target)\n",
    "        R = self.dfs(root.right, target)\n",
    "        \n",
    "        if L == -1 and R == -1:\n",
    "            return -1\n",
    "        return max(L , R) + 1\n",
    "\n",
    "    def find_LCA(self, root: TreeNode, p: int, q: int) -> TreeNode:\n",
    "        if root==None or root.val==p or root.val==q:\n",
    "            return root\n",
    "        L = self.find_LCA(root.left, p, q)\n",
    "        R = self.find_LCA(root.right, p, q)\n",
    "        if L and R:\n",
    "            return root\n",
    "        elif L and R==None:\n",
    "            return L\n",
    "        elif L == None and R:\n",
    "            return R\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        def LCA(node, p, q):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.val == p or node.val == q:\n",
    "                return node\n",
    "            left = LCA(node.left, p, q)\n",
    "            right = LCA(node.right, p, q)\n",
    "            if left and right:\n",
    "                return node\n",
    "            return left or right\n",
    "        \n",
    "        def getDist(node, target):\n",
    "            if not node:\n",
    "                return -1\n",
    "            if node.val == target:\n",
    "                return 0\n",
    "            left = getDist(node.left, target)\n",
    "            right = getDist(node.right, target)\n",
    "            print(node.val, left, right)\n",
    "            if left >= 0:\n",
    "                return left + 1\n",
    "            elif right >= 0: \n",
    "                return right + 1\n",
    "            return -1\n",
    "        \n",
    "        lca = LCA(root, p, q)\n",
    "        # print(lca.val)\n",
    "        pDist = getDist(lca, p)\n",
    "        qDist = getDist(lca, q)\n",
    "        # print(pDist, qDist)\n",
    "        return pDist + qDist\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        # 找到从根到给定值的路径\n",
    "        def findPath(node, val, path):\n",
    "            if not node:\n",
    "                return False\n",
    "            # 将当前节点加入路径\n",
    "            path.append(node)\n",
    "            # 如果当前节点的值与给定值匹配，则返回True\n",
    "            if node.val == val:\n",
    "                return True\n",
    "            # 否则，在左或右子树中查找\n",
    "            if (findPath(node.left, val, path) or findPath(node.right, val, path)):\n",
    "                return True\n",
    "            # 如果左、右子树都没有找到，则从路径中删除当前节点并返回False\n",
    "            path.pop()\n",
    "            return False\n",
    "        \n",
    "        pathP, pathQ = [], []\n",
    "        findPath(root, p, pathP)\n",
    "        findPath(root, q, pathQ)\n",
    "        \n",
    "        # 寻找两路径的不同部分\n",
    "        i = 0\n",
    "        while i < len(pathP) and i < len(pathQ) and pathP[i] == pathQ[i]:\n",
    "            i += 1\n",
    "        \n",
    "        # 计算两节点之间的距离\n",
    "        return (len(pathP) - i) + (len(pathQ) - i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        res=0\n",
    "        def dfs(r):\n",
    "            if not r:return 0\n",
    "            nonlocal res\n",
    "            ll=dfs(r.left)\n",
    "            rr=dfs(r.right)\n",
    "            if ll==-1 or rr==-1:return -1\n",
    "            if r.val==p or r.val==q:\n",
    "                if ll==0 and rr==0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    res=ll+rr\n",
    "                    return -1\n",
    "            else:\n",
    "                if ll==0 and rr==0:return 0\n",
    "                if ll!=0 and rr!=0:\n",
    "                    res=ll+rr\n",
    "                    return -1\n",
    "                return ll+rr+1\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(root):\n",
    "            if root is None: return False, 0\n",
    "            l0, n0 = dfs(root.left)\n",
    "            l1, n1 = dfs(root.right)\n",
    "            cur = root.val == p or root.val == q\n",
    "            if (l0 and l1) or cur and (l0 or l1):\n",
    "                self.ans = n0 + n1\n",
    "                return False, 0\n",
    "            if l0 or cur: \n",
    "                return True, n0 + 1\n",
    "            if l1 or cur: \n",
    "                return True, n1 + 1\n",
    "            return False, 0\n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        if p == q:\n",
    "            return 0\n",
    "\n",
    "        def lca(root, p, q):\n",
    "            if root is None:\n",
    "                return root\n",
    "            left = lca(root.left, p, q)\n",
    "            right = lca(root.right, p, q)\n",
    "            if root.val == p or root.val == q:\n",
    "                return root\n",
    "            if left and right:\n",
    "                return root\n",
    "            return left or right\n",
    "\n",
    "        def dfs(root, target):\n",
    "            if root is None:\n",
    "                return -1\n",
    "            if root.val == target:\n",
    "                return 0\n",
    "            left = dfs(root.left, target)\n",
    "            right = dfs(root.right, target)\n",
    "            if left == -1 and right == -1:\n",
    "                return -1\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        ancestor = lca(root, p, q)\n",
    "        d1 = dfs(ancestor, p)\n",
    "        d2 = dfs(ancestor, q)\n",
    "        # print(ancestor.val, d1, d2)\n",
    "        return d1 + d2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        if p == q:\n",
    "            return 0\n",
    "        global res\n",
    "        def dfs(n):\n",
    "            global res\n",
    "            if n == None:\n",
    "                return (0,0)\n",
    "            l1,l2 = dfs(n.left)\n",
    "            r1,r2 = dfs(n.right)\n",
    "            if n.val != p and n.val != q:\n",
    "                if l1 == 0 and r1 == 0:\n",
    "                   # print(f\"val = {n.val} return (0,0)\")\n",
    "                    return (0,0)\n",
    "                elif l1 == 1 and r1 == 1:\n",
    "                    res = l2 + r2 + 2\n",
    "                  #  print(f\"val = {n.val} return (0,0)\")\n",
    "                    return (0,0)\n",
    "                elif l1 == 1 and r1 == 0:\n",
    "                   # print(f\"val = {n.val} return (1,{l2+1})\")\n",
    "                    return (1,l2+1)\n",
    "                else:\n",
    "                  #  print(f\"val = {n.val} return (1,{r2+1})\")\n",
    "                    return (1,r2+1)\n",
    "            else:\n",
    "                if l1 == 0 and r1 == 0:\n",
    "                  #  print(f\"val = {n.val} return (1,0)\")\n",
    "                    return (1,0)\n",
    "                elif l1 == 1:\n",
    "                    res = l2 + 1\n",
    "                  #  print(f\"val = {n.val} return (0,0)\")\n",
    "                    return (0,0)\n",
    "                elif r1 == 1:\n",
    "                    res = r2 + 1\n",
    "                  #  print(f\"val = {n.val} return (0,0)\")\n",
    "                    return (0,0)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        if p == q: return 0\n",
    "        def search(node: TreeNode, p, q, depth) -> int:\n",
    "            if not node: return 0\n",
    "\n",
    "            l = search(node.left, p, q, depth+1)\n",
    "            r = search(node.right, p, q, depth+1)\n",
    "\n",
    "            if node.val == p or node.val == q:\n",
    "                if not l and not r: return depth\n",
    "                else:\n",
    "                    return l + r - depth\n",
    "            else:\n",
    "                if l and r :\n",
    "                    return l + r - 2*depth \n",
    "                else:\n",
    "                    return l + r            \n",
    "\n",
    "        return search(root, p, q, 0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        LCA = None\n",
    "\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return False\n",
    "\n",
    "            nonlocal LCA\n",
    "\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "\n",
    "            if node.val == p or node.val == q:\n",
    "\n",
    "                if left or right:\n",
    "                    if LCA is None:\n",
    "                        LCA = node\n",
    "\n",
    "                return True\n",
    "            else:\n",
    "                if left and right:\n",
    "                    if LCA is None:\n",
    "                        LCA = node\n",
    "\n",
    "                return left or right\n",
    "\n",
    "        n_edge = 0\n",
    "\n",
    "        def distance(node, dist):\n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "            nonlocal n_edge\n",
    "            if node.val == p:\n",
    "                n_edge += dist\n",
    "            elif node.val == q:\n",
    "                n_edge += dist\n",
    "            distance(node.left, dist + 1)\n",
    "            distance(node.right, dist + 1)\n",
    "\n",
    "        if q == p:\n",
    "            return 0\n",
    "\n",
    "        dfs(root)\n",
    "        print(LCA.val)\n",
    "        distance(LCA, 0)\n",
    "\n",
    "        return n_edge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        if p == q:\n",
    "            return 0\n",
    "        que = defaultdict(list)\n",
    "\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                que[node.val].append(node.left.val)\n",
    "                que[node.left.val].append(node.val)\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                que[node.val].append(node.right.val)\n",
    "                que[node.right.val].append(node.val)\n",
    "                dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        ans = 0\n",
    "\n",
    "        def f(node, fa, d):\n",
    "            nonlocal ans \n",
    "            if ans:\n",
    "                return \n",
    "            if node == q:\n",
    "                ans = d \n",
    "                return \n",
    "            for nxt in que[node]:\n",
    "                if nxt != fa:\n",
    "                    f(nxt, node, d + 1)\n",
    "        \n",
    "        f(p, -1, 0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], p: int, q: int) -> int:\n",
    "        if p == q:\n",
    "            return 0\n",
    "        que = defaultdict(list)\n",
    "\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                que[node.val].append(node.left.val)\n",
    "                que[node.left.val].append(node.val)\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                que[node.val].append(node.right.val)\n",
    "                que[node.right.val].append(node.val)\n",
    "                dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        ans = 0\n",
    "\n",
    "        def f(node, fa, d):\n",
    "            nonlocal ans \n",
    "            if ans:\n",
    "                return \n",
    "            if node == q:\n",
    "                ans = d \n",
    "                return \n",
    "            for nxt in que[node]:\n",
    "                if nxt != fa:\n",
    "                    f(nxt, node, d + 1)\n",
    "        \n",
    "        f(p, -1, 0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findDistance(self, root: Optional[TreeNode], u: int, v: int) -> int:\n",
    "        if u == v: return 0\n",
    "        pa = defaultdict(lambda: -1)\n",
    "        pa[root.val] = -1\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        def traverse(node, l = 0):\n",
    "            d[node.val] = l\n",
    "            if node.left:\n",
    "                pa[node.left.val] = node.val\n",
    "                traverse(node.left,l + 1)\n",
    "            if node.right:\n",
    "                pa[node.right.val] = node.val\n",
    "                traverse(node.right, l + 1)\n",
    "        \n",
    "        traverse(root)\n",
    "        n = len(pa.keys())\n",
    "        m = n.bit_length() - 1\n",
    "        \n",
    "        f = {}\n",
    "        for node in pa:\n",
    "            f[node] = [pa[node]] + [-1] * m\n",
    "        \n",
    "        for i in range(m):\n",
    "            for x in pa:\n",
    "                y = f[x][i]\n",
    "                if y != -1:\n",
    "                    f[x][i + 1] = f[y][i]\n",
    "        \n",
    "\n",
    "        du,dv = d[u], d[v]\n",
    "        u,v = (v,u) if du < dv else (u,v)\n",
    "        x = v\n",
    "        df = abs(du - dv)\n",
    "        res = du + dv\n",
    "        for i in range(df.bit_length()):\n",
    "            if df >> i & 1:\n",
    "                u = f[u][i]\n",
    "        if u != v:\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                if f[u][i] != f[v][i]:\n",
    "                    u = f[u][i]\n",
    "                    v = f[v][i]\n",
    "            x = f[u][0]\n",
    "        return res - 2 * d[x]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
